POZOR:
Da ne bo težav pri testiranju, pri vseh podnalogah začnemo z
class Ulomek(Ulomek):To pomeni, da se v razred "skopirajo" vse definicije, ki ste jih v razred Ulomek napisali prej. Seveda pa 1. podnalogo še vedno začnemo z
class Ulomek():Druga možnost pa je, da podnaloge vedno začnemo z
class Ulomek():a potem v razred vedno napišemo vse metode, ki smo jih definirali v vseh prejšnjih podnalogah!
Izven razreda sestavite funkcijo gcd(m, n), ki izračuna največji skupni
delitelj števil m in n.
def gcd(m, n): while n != 0: m, n = n, m % n return m
Definirajte razred Ulomek, s katerim predstavimo ulomek. Števec in
imenovalec sta celi števili, pri čemer je morebiten negativen predznak
vedno v števcu. Komponenti naj se imenujeta _st in _im.
Ulomki naj bodo vedno okrajšani.
Najprej definirajte konstruktor __init__(self, st, im).
class Ulomek: def __init__(self, st, im): if im < 0: st, im = -st, -im d = gcd(st, im) self._st = st // d self._im = im // d
Definirajte metodo __str__, ki predstavi ulomek v obliki "st/im".
class Ulomek(Ulomek): def __str__(self): return "{0}/{1}".format(self._st, self._im)
Definirajte metodo __eq__, ki vrne True če sta dva ulomka
enaka, in False sicer.
class Ulomek(Ulomek): def __eq__(self, other): return self._st == other._st and self._im == other._im
Definirajte metodo __add__, ki vrne vsoto dveh ulomkov.
Ko definirate to metodo, lahko ulomke seštevate kar z operatorjem +.
Na primer:
>>> print(Ulomek(1, 6) + Ulomek(1, 4))
5/12class Ulomek(Ulomek): def __add__(self, other): a, b = self._st, self._im c, d = other._st, other._im return Ulomek(a * d + b * c, b * d)
Definirajte metodo __sub__, ki vrne razliko dveh ulomkov.
Ko definirate to metodo, lahko ulomke odštevate kar z operatorjem -.
class Ulomek(Ulomek): def __sub__(self, other): a, b = self._st, self._im c, d = other._st, other._im return Ulomek(a * d - b * c, b * d)
Definirajte metodo __mul__, ki vrne zmnožek dveh ulomkov.
Ko definirate to metodo, lahko ulomke množite kar z operatorjem *.
class Ulomek(Ulomek): def __mul__(self, other): a, b = self._st, self._im c, d = other._st, other._im return Ulomek(a * c, b * d)
Definirajte metodo __truediv__, ki vrne kvocient dveh ulomkov.
Ko definirate to metodo, lahko ulomke delite kar z operatorjem /.
class Ulomek(Ulomek): def __truediv__(self, other): a, b = self._st, self._im c, d = other._st, other._im return Ulomek(a * d, b * c)
Definirajte funkcijo priblizek(n), ki vrne vsoto
def priblizek(n): def fakulteta(i): return 1 if i == 0 else i * fakulteta(i - 1) return sum((Ulomek(1, fakulteta(i)) for i in range(n + 1)), Ulomek(0, 1))
Dan je razred Drevo, ki predstavlja dvojiško drevo. Za osnovno vzemite
naslednjo kodo:
class Drevo:
def __init__(self, *args, **kwargs):
if args:
self.prazno = False
self.vsebina = args[0]
self.levo = kwargs.get('levo', Drevo())
self.desno = kwargs.get('desno', Drevo())
else:
self.prazno = True
def __repr__(self, zamik=''):
if self.prazno:
return 'Drevo()'.format(zamik)
elif self.levo.prazno and self.desno.prazno:
return 'Drevo({1})'.format(zamik, self.vsebina)
else:
return 'Drevo({1},\n{0} levo = {2},\n{0} desno = {3})'.\
format(
zamik,
self.vsebina,
self.levo.__repr__(zamik + ' '),
self.desno.__repr__(zamik + ' ')
)
def __eq__(self, other):
return ((self.prazno and other.prazno) or
(not self.prazno and not other.prazno and
self.vsebina == other.vsebina and
self.levo == other.levo and
self.desno == other.desno))Konstruktor je že implementiran; prav tako metodi __repr__ in __eq__.
Drevo na spodnji (ASCII art) sliki:
5
/ \
3 2
/ / \
1 6 9sestavimo takole:
>>> d = Drevo(5,
levo=Drevo(3, levo=Drevo(1)),
desno=Drevo(2, levo=Drevo(6), desno=Drevo(9)))Razredu dodajte metodo vsota(self), ki vrne vsoto vseh števil v drevesu.
Zgled (kjer je d kot zgoraj):
>>> d.vsota()
26class Drevo: def __init__(self, *args, **kwargs): if args: self.prazno = False self.vsebina = args[0] self.levo = kwargs.get('levo', Drevo()) self.desno = kwargs.get('desno', Drevo()) else: self.prazno = True def __repr__(self, zamik=''): if self.prazno: return 'Drevo()'.format(zamik) elif self.levo.prazno and self.desno.prazno: return 'Drevo({1})'.format(zamik, self.vsebina) else: return 'Drevo({1},\n{0} levo = {2},\n{0} desno = {3})'.\ format( zamik, self.vsebina, self.levo.__repr__(zamik + ' '), self.desno.__repr__(zamik + ' ') ) def __eq__(self, other): return ((self.prazno and other.prazno) or (not self.prazno and not other.prazno and self.vsebina == other.vsebina and self.levo == other.levo and self.desno == other.desno)) def vsota(self): if self.prazno: return 0 else: return self.vsebina + self.levo.vsota() + self.desno.vsota()
Dodajte metodo stevilo_listov(self), ki vrne število listov v drevesu.
Zgled (kjer je d kot zgoraj):
>>> d.stevilo_listov()
3class Drevo(): def __init__(self, *args, **kwargs): if args: self.prazno = False self.vsebina = args[0] self.levo = kwargs.get('levo', Drevo()) self.desno = kwargs.get('desno', Drevo()) else: self.prazno = True def __repr__(self, zamik=''): if self.prazno: return 'Drevo()'.format(zamik) elif self.levo.prazno and self.desno.prazno: return 'Drevo({1})'.format(zamik, self.vsebina) else: return 'Drevo({1},\n{0} levo = {2},\n{0} desno = {3})'. \ format( zamik, self.vsebina, self.levo.__repr__(zamik + ' '), self.desno.__repr__(zamik + ' ') ) def __eq__(self, other): return ((self.prazno and other.prazno) or (not self.prazno and not other.prazno and self.vsebina == other.vsebina and self.levo == other.levo and self.desno == other.desno)) def vsota(self): if self.prazno: return 0 else: return self.vsebina + self.levo.vsota() + self.desno.vsota() def stevilo_listov(self): if self.prazno: return 0 elif self.levo.prazno and self.desno.prazno: return 1 else: return self.levo.stevilo_listov() + self.desno.stevilo_listov()
Dodajte metodo minimum(self), ki vrne najmanjše število v drevesu.
Če je drevo prazno, naj metoda vrne None. Zgled (kjer je d kot
zgoraj):
>>> d.minimum()
1
>>> Drevo().minimum()
Noneclass Drevo(Drevo): def __init__(self, *args, **kwargs): if args: self.prazno = False self.vsebina = args[0] self.levo = kwargs.get('levo', Drevo()) self.desno = kwargs.get('desno', Drevo()) else: self.prazno = True def __repr__(self, zamik=''): if self.prazno: return 'Drevo()'.format(zamik) elif self.levo.prazno and self.desno.prazno: return 'Drevo({1})'.format(zamik, self.vsebina) else: return 'Drevo({1},\n{0} levo = {2},\n{0} desno = {3})'. \ format( zamik, self.vsebina, self.levo.__repr__(zamik + ' '), self.desno.__repr__(zamik + ' ') ) def __eq__(self, other): return ((self.prazno and other.prazno) or (not self.prazno and not other.prazno and self.vsebina == other.vsebina and self.levo == other.levo and self.desno == other.desno)) def vsota(self): if self.prazno: return 0 else: return self.vsebina + self.levo.vsota() + self.desno.vsota() def stevilo_listov(self): if self.prazno: return 0 elif self.levo.prazno and self.desno.prazno: return 1 else: return self.levo.stevilo_listov() + self.desno.stevilo_listov() def minimum(self): if self.prazno: return None else: # Vrednost izraza `a or b` je `a`, če je `bool(a) == True`, # in `b` sicer. Torej, to je ekvivalentno izrazu `a if a else b`. # Opomba: `bool(None) == False`. levi_minimum = self.levo.minimum() or float('inf') desni_minimum = self.desno.minimum() or float('inf') return min(self.vsebina, levi_minimum, desni_minimum)
V neki mafijski organizaciji so člani urejeni hierarhično. Vsakdo razen botra (vrhovnega šefa) ima natanko enega nadrejenega. Vsak mafijec ima lahko pod seboj največ dva podrejena (levega in desnega). Primer takšne mafijske organizacije:
mafija = Drevo('Salvatore', 320,
levo=Drevo('Bernardo', 200,
levo=Drevo('Matteo', 50),
desno=Drevo('Carlo', 100,
levo=Drevo('Rosalia', 70),
desno=Drevo('Tommaso', 50))),
desno=Drevo('Francesco', 120,
levo=Drevo('Giuseppe', 70),
desno=Drevo('Antonio', 60)))Mafijci morajo zbirati denar s kriminalnimi dejavnostmi. Tisti, ki imajo podrejene, pa ga poleg tega poberejo še od svojih podrejenih. Ves “prisluženi” in prejeti denar morajo oddati svojemu nadrejenemu.
Boter je posumil, da nekateri člani goljufajo. Nekaj denarja, ki ga
poberejo od podrejenih, zadržijo zase. Od vsakega člana je pridobil
podatek o tem, koliko denarja je oddal naprej. Podatke je shranil v
podatkovno strukturo Drevo, ki je že implementirana.
Botra zanima, koliko denarja zaradi goljufov “ponikne”. Želi, da
sestavite metodo koliko_ponikne(self), ki vrne skupno vsoto denarja,
ki ponikne. Primer (če mafija ustreza zgornjemu drevesu):
>>> mafija.koliko_ponikne()
30class Drevo: def __init__(self, *args, **kwargs): if len(args) > 0: self.prazno = False self.ime = args[0] self.vrednost = args[1] self.levo = kwargs.get('levo', Drevo()) self.desno = kwargs.get('desno', Drevo()) else: self.prazno = True def __repr__(self): if self.prazno: return 'Drevo()' else: opis = repr(self.ime) + ', ' + repr(self.vrednost) if not self.levo.prazno: opis += ', levo={0}'.format(self.levo) if not self.desno.prazno: opis += ', desno={0}'.format(self.desno) return 'Drevo({0})'.format(opis) def get_vrednost(self): return self.vrednost if not self.prazno else 0 def koliko_ponikne(self): if self.prazno: return 0 utajil = max(self.levo.get_vrednost() + self.desno.get_vrednost() - self.get_vrednost(), 0) return utajil + self.levo.koliko_ponikne() + self.desno.koliko_ponikne()
Ko je boter dognal, koliko denarja ponikne, je totalno po████. Pri
priči hoče imeti imena vseh goljufov! Napišite metodo goljufi(self),
ki vrne množico goljufov. Vsak goljuf naj bo predstavljen z naborom.
Prva kompotenta naj bo ime goljufa, druga komponenta pa količina denarja,
ki ga je utajil. Primer:
>>> mafija.goljufi()
{(’Carlo’, 20), (’Francesco’, 10)}class Drevo: def __init__(self, *args, **kwargs): if len(args) > 0: self.prazno = False self.ime = args[0] self.vrednost = args[1] self.levo = kwargs.get('levo', Drevo()) self.desno = kwargs.get('desno', Drevo()) else: self.prazno = True def __repr__(self): if self.prazno: return 'Drevo()' else: opis = repr(self.ime) + ', ' + repr(self.vrednost) if not self.levo.prazno: opis += ', levo={0}'.format(self.levo) if not self.desno.prazno: opis += ', desno={0}'.format(self.desno) return 'Drevo({0})'.format(opis) def get_vrednost(self): return self.vrednost if not self.prazno else 0 def goljufi(self): if self.prazno: return set() utajil = max(self.levo.get_vrednost() + self.desno.get_vrednost() - self.get_vrednost(), 0) return ({(self.ime, utajil)} if utajil > 0 else set()) | self.levo.goljufi() | self.desno.goljufi()
Botru se dozdeva, da so najbolj pridne majhne ribe. To so tisti mafijci,
ki nimajo pod seboj nobenega podrejenega. Tistim, ki imajo podrejene, se
reče velike ribe. Napišite metodo zasluzek(self), ki vrne par (nabor)
dveh števili, pri čemer je:
Primer:
>>> mafija.zasluzek()
(300, 50)class Drevo: def __init__(self, *args, **kwargs): if len(args) > 0: self.prazno = False self.ime = args[0] self.vrednost = args[1] self.levo = kwargs.get('levo', Drevo()) self.desno = kwargs.get('desno', Drevo()) else: self.prazno = True def __repr__(self): if self.prazno: return 'Drevo()' else: opis = repr(self.ime) + ', ' + repr(self.vrednost) if not self.levo.prazno: opis += ', levo={0}'.format(self.levo) if not self.desno.prazno: opis += ', desno={0}'.format(self.desno) return 'Drevo({0})'.format(opis) def get_vrednost(self): return self.vrednost if not self.prazno else 0 def zasluzek(self): if self.prazno: return 0, 0 l_male, l_velike = self.levo.zasluzek() d_male, d_velike = self.desno.zasluzek() mala = self.levo.prazno and self.desno.prazno prispevek = max(self.get_vrednost() - self.levo.get_vrednost() - self.desno.get_vrednost(), 0) m, v = l_male + d_male, l_velike + d_velike if mala: m += prispevek else: v += prispevek return m, v
Definirajte razred Polinom, s katerim predstavimo polinom v
spremenljivki Polinom([7, 2, 0, 1]).
Razmislite, kaj predstavlja Polinom([]). Zadnji koeficient v seznamu
mora biti neničelen.
Sestavite konstruktor __init__(koef), ki nastavi tabelo koeficientov.
class Polinom: def __init__(self, koef): # že na začetku se znebimo vseh ničelnih vodilnih koeficientov zadnji = len(koef) while zadnji > 0 and koef[zadnji - 1] == 0: zadnji -= 1 self._koef = koef[:zadnji]
Sestavite metodo stopnja, ki vrne stopnjo polinoma. Stopnja ničelnega
polinoma je v matematiki po dogovoru
class Polinom(Polinom): def stopnja(self): return len(self._koef) - 1
Sestavite metodo __eq__ za primerjanje polinomov.
class Polinom(Polinom): def __eq__(self, other): return self._koef == other._koef
Sestavite metodo __add__ za seštevanje polinomov.
Pozor: pri seštevanju se lahko zgodi, da se nekateri začetni
koeficienti pokrajšajo:
class Polinom(Polinom): def __add__(self, other): # predpostavimo, da ima levi polinom vsaj toliko členov kot desni if len(self._koef) < len(other._koef): return other + self # nato vzamemo levi polinom in kosoma prištevamo desnega koef_vsote = self._koef for n, a in enumerate(other._koef): koef_vsote[n] += a return Polinom(koef_vsote)
Sestavite metodo __mul__ za množenje polinomov.
class Polinom(Polinom): def __mul__(self, other): # če je eden od polinomov ničelen, je ničelen tudi produkt if not self._koef or not other._koef: return Polinom([]) # oba polinoma z ničlami podaljšamo do iste dolžine levi = self._koef + len(other._koef) * [0] desni = other._koef + len(self._koef) * [0] koef_prod = [sum(levi[i] * desni[n - i] for i in range(n + 1)) for n in range(len(levi))] return Polinom(koef_prod)
Sestavite metodo __str__, ki predstavi polinom v čitljivi obliki.
>>> print(Polinom([1, -2, 3, -1]))
-x^3 + 3 x^2 - 2 x + 1
>>> print(Polinom([-1, 0, 0, 1]))
x^3 - 1class Polinom(Polinom): def __str__(self): def monom(a, n): # Sestavimo si člen za monom. Na začetku in na koncu damo še oglate # oklepaje, ki jih bomo na koncu sicer pobrisali, da bomo vmes lahko # na poseben način obravnavali nekatere kombinacije znakov. monom = "[{0} x^{1}]".format(a, n) # popravimo potence in koeficiente monom = monom.replace("^1]", "") # ^1 pobrišemo le na koncu niza monom = monom.replace(" x^0", "") # pobrišemo presledek pred x^0 monom = monom.replace("[1 x", "x") # 1 mora biti na začetku monoma monom = monom.replace("-1 x", "-x") monom = monom.replace("[", "").replace("]", "") return monom # "seštejemo" vse momone z neničelnimi koeficienti # pred tem moramo koeficiente obrniti v vrstni red kot v izpisu niz = " + ".join(reversed([monom(a, n) for n, a in enumerate(self._koef) if a != 0])) niz = niz.replace("+ -", "- ") # popravimo negativne koeficiente # če smo dobili niz, ga vrnemo, sicer izpišemo ničelni polinom return niz or "0"
Vektorjem, ki vsebujejo veliko število ničelnih elementov, pravimo redki vektorji. Namesto običajne predstavitve, pri kateri navedemo vse elemente vektorja, lahko uporabimo bolj kompaktno predstavitev, kjer ničelne elemente izpustimo, za neničelne pa si zapomnimo, na katerih mestih so.
Primer: Vektor
a = [1, 0, 0, 0, 0, 5, 1, 0, 0, 0, 4, 0, 0]lahko namesto v obliki dolgega seznama z veliko ničlami zapišemo v kompaktni obliki kot slovar, kjer so ključi indeksi neničelnih elementov iz dolgega zapisa:
r = {0: 1, 10: 4, 5: 5, 6: 1}Vrstni red indeksov seveda ni pomemben, saj imamo slovar. Ničelni vektor
predstavimo kar s praznim slovarjem {}.
Napišite funkcijo stisni(vektor), ki sprejme vektor kot seznam števil
ter vrne redko obliko vektorja, tj. slovar, v katerem so ključi indeksi
neničelnih vrednosti, vrednosti pa te neničelne vrednosti.
Primer:
>>> stisni([1, 0, 0, 0, 0, 5, 1, 0, 0, 0, 4])
{0: 1, 10: 4, 5: 5, 6: 1}
>>> stisni([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 99])
{0: 1, 15: 99}def stisni(vektor): '''vrne redko obliko vektorja, v obliki indeks : vrednost''' sv = dict() for i, x in enumerate(vektor): if x != 0: # zanimajo nas le neničelni elementi sv[i] = x return sv
Definirajte razred Vektor, s katerim bomo predstavili redke vektorje.
Sestavite konstruktor, ki kot parameter sprejme vektor v stisnjeni obliki
(slovar) ter ga priredi atributu elementi.
Sestavite še metodo __len__, ki vrne število neničelih elementov redkega
vektorja. Metoda nima argumentov (razen obveznega argumenta self, ki pove,
da gre za metodo danega razreda). Metoda __len__ se bo izvedla, kadar
bomo na objektu tipa Vektor uporabili Pythonovo vgrajeno funkcijo len,
kot je prikazano v spodnjem primeru.
Primer:
>>> a = Vektor({0: 1, 10: 4, 5: 5, 6: 1})
>>> a.elementi
{0: 1, 10: 4, 5: 5, 6: 1}
>>> len(a)
4class Vektor: def __init__(self, data): self.elementi = data def __len__(self): return len(self.elementi)
Definirajte metodi __add__ in __sub__, s katerima boste definirali
operatorja + in - nad objekti tipa Vektor. Gre za običajno
seštevanje in odštevanje vektorjev, le da morate upoštevati, da seštevamo
oz. odštevamo redki obliki, ki sta predstavljeni s slovarjema.
Vsaka od metod sprejema en argument in sicer drugi vektor, ki nastopa v
aritmetični operaciji, vrne pa naj nov objekt tipa Vektor, ki je vsota
oz. razlika danih vektorjev.
Nasvet: Upoštevajte, da so v rezultatu lahko neničelne vrednosti le na tistih indeksih, pri katerih je neničeln vsaj en od obeh operandov – pomagajte si z unijo obeh množic indeksov.
Primer:
>>> a = Vektor({0: 1})
>>> b = Vektor({0: 1, 3: 1})
>>> c = a + b
>>> c.elementi
{0: 2, 3: 1}class Vektor(Vektor): def __add__(self, other): data = dict() keys = set(self.elementi).union(other.elementi) # set iz slovarja pobere le ključe! for k in keys: # poberemo k kar iz obeh, če ga ni, vzamemo 0 v = self.elementi.get(k, 0) + other.elementi.get(k, 0) if v != 0: # če se vrednosti nista izničili (negativna št!) data[k] = v return Vektor(data) def __sub__(self, other): data = dict() keys = set(self.elementi).union(other.elementi) # unija ključev, ker je set(slovar) istio kot set(slovar.keys()) for k in keys: v = self.elementi.get(k, 0) - other.elementi.get(k, 0) if v != 0: # če se vrednosti nista izničili data[k] = v return Vektor(data)
Definirajte še metodo razsiri, ki vrne običajno (dolgo) obliko
vektorja. Pri tem se razširjena oblika ne sme končati z 0, saj drugače
razširitev ni enolična (glej drugi primer!)
Primer:
>>> a = Vektor(stisni([1, 0, 0, 0, 0, 0, 0, 0, 9]))
>>> a.elementi
{0: 1, 8: 9}
>>> a.razsiri()
[1, 0, 0, 0, 0, 0, 0, 0, 9]
>>> Vektor(stisni([1, 0, 0, 0])).razsiri()
[1]class Vektor(Vektor): def razsiri(self): '''razpihne redki vektor v "običajno" obliko''' if self.elementi == dict(): return list() # prazen seznam else: # maksimalni indeks je maksimalna vrednost ključa v slovarju # vrednosti za vsak indeks bodo bodisi 0 bodisi ustrezne vrednosti iz slovarja return [self.elementi.get(i, 0) for i in range(max(self.elementi) + 1)]